﻿#include "stdafx.h"
#include "RemoveNthFromEnd.h"

using namespace std;

namespace algorithm {
ListNode* CRemoveNthFromEnd::Remove(ListNode* head, int n)
{
    if (n < 0) {
        return head;
    }
    /* 双指针实现 */
    ListNode temp;
    temp.next = head;
    ListNode* left = &temp;
    ListNode* right = left;
    /* left、right指针建立间隔n，此时left指针的next则表示距离right指针第n个节点 */
    for (int i = 0; i < n; i++)
    {
        if (right)
        {
            right = right->next;
        }
    }
    /* 将right指针移动到尾节点，此时left指针的next则表示距离尾节点第n个节点 */
    while (right->next) {
        right = right->next;
        left = left->next;
    }
    /* 删除left指针的next节点 */
    auto node = left->next->next;
    delete left->next;
    left->next = node;
    /* 返回头节点 */
    return temp.next;
}
}
